/**
 * 普利姆算法：
 * 和kruskal不同的是，这个算法将顶点置于优先的位置，根据近邻的边的大小，选择一个边权最小的顶点
 * 加入到确定顶点集合，然后将顶点集合不断扩大最后形成树
 * 不管是Kruskal算法还是Prime算法去，其核心都是切分定理。
切分定理：
切分
把图中的节点分为两部分，称为一个切分（Cut）；
横切边
如果一个边的两个端点，属于切分（Cut）不同的两边，这个边称为横切边（Crossing Edge）;
切分定理
给定任意切分，横切边中权值最小的边必然属于最小生成树；

切分定理的证明可使用反正法，这里不给出证明，证明不了只需要知道切分定理的正确性就能推出Prime算法的正确性。
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#define N  100
#define INF 65535
//无向图邻接矩阵数据结构 
typedef  struct {
    int vcount;//顶点数
    char  vexs[N];     // 顶点信息
    int  arcs[N][N]; //带权关系矩阵，就是边
} GraphMatrix;
/*
图初始化-邻接矩阵
6 10
A B C D E F
{{0,5,6,4,0,0},
{5,0,1,2,0,0},
{6,1,0,2,5,3},
{4,2,2,0,0,4},
{0,0,5,0,0,4},
{0,0,3,4,4,0},}
代码中将所有0改为INF无穷大
*/
GraphMatrix* initGraphMatrix()
{
    GraphMatrix* G;
    G = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    G->vcount = 6;//顶点数
    char vertex[]={'A' ,'B', 'C', 'D', 'E', 'F'};//顶点数据
    int edges[6][6]={
                    {INF,5,6,4,INF,INF},
                    {5,INF,1,2,INF,INF},
                    {6,1,INF,2,5,3},
                    {4,2,2,INF,INF,4},
                    {INF,INF,5,INF,INF,4},
                    {INF,INF,3,4,4,INF},
                };
    for (int i = 0; i < 6; i++){     //创建矩阵
        G->vexs[i]=vertex[i];
        for (int j = 0; j < 6; j++){
            G->arcs[i][j] = edges[i][j];//初始化矩阵
        }
    }
    return G;
}
/**
 * 
 * 没有使用parent数组，parent数组用来记录父节点，从而可以还原出整棵树
 * @param G 图
 * @param v 开始节点
 */
void prime(GraphMatrix* G,int v) {
    int visit[N]={0};           //点是否访问过，未访问0，访问1
    visit[v] = 1;               //起始点已经访问过
 
    int short_length[N];//访问过的点的集合到未访问过点的集合的最小路径
 
    for (int i = 0; i < G->vcount; i++) 
        short_length[i] = G->arcs[v][i];        //初始化，就是起点到其他点的长度
    short_length[v] = 0;        //起始点到自己路径为0
 
    printf("%d", v); //打印起始点
    //开始遍历，通过边，寻找其他路径最短的顶点
    //i只用作遍历次数，不表示任何下标
    for (int i = 1; i < G->vcount; i++){//有n个点，那最短路径就是n-1个边组成，遍历n-1次
        int min_length = INF;//最短路径初始化为INF
        int k=0;//记录最小值节点的下标
        for (int j = 0; j < G->vcount; j++) {   //在所有未访问过的边里找到最短路径
            if (min_length > short_length[j] && visit[j] == 0) {
                k = j;
                min_length = short_length[j];
            }
        }
        visit[k] = 1;  printf("-%d", k);//将这个点加入已访问过的集合，并打印
        for (int j = 0; j < G->vcount; j++) {
            //和short_length数组比较的是，“新加入的这个节点”到其他节点的距离
            if (visit[j] == 0 && short_length[j] > G->arcs[k][j])
                short_length[j] = G->arcs[k][j];
        }//更新未访问过点的最短路径
    }
    return;
}
int main(int argc,char* argv[]){
    GraphMatrix* G = initGraphMatrix();
    prime(G,0);
}